package nf.graph;

import java.util.*;

public class IsomorphicComparator implements Comparator<Graph>
{
	public int compare(Graph a, Graph b)
	{
		return findRelation(a, b);
	}
	
	private int findRelation(Graph a, Graph b)
	{
		long diff = a.size() - b.size();
		
		if (diff != 0)
			return (int) diff; // safe as size() returns an int
		
		diff = a.edgeCount() - b.edgeCount();
		if (diff != 0) {
			return (diff < 0)
				? -1
				: 1;
		}
		
		int nodeCount = a.size();
		ArrayList<Node> na = new ArrayList<Node>(a);
		ArrayList<Node> nb = new ArrayList<Node>(b);
		
		List<Map<Node, Node>> permutations = permute(na);
		for (Map<Node, Node> p : permutations) {
			boolean found = true;
			
			for (Map.Entry<Node, Node> e : p.entrySet()) {
				Node aNode = e.getKey();
				Node bNode = b.getNode(e.getValue().getName());
				
				if (aNode.getDegree() != bNode.getDegree()) {
					found = false;
					break;
				}
				
				for (Node neighbor : aNode.getNeighbors()) {
					if (!b.connected(bNode, p.get(neighbor))) {
						found = false;
						break;
					}
				}
			}
			
			if (found)
				return 0;
		}
		
		double dblDiff = a.getDensity() - b.getDensity();
		if (dblDiff != 0)
			return (dblDiff < 0) ? -1 : 1;
			
		dblDiff = a.getAverageDegree() - b.getAverageDegree();
		if (dblDiff != 0)
			return (dblDiff < 0) ? -1 : 1;
		
		return a.hashCode() - b.hashCode();
	}
	
	private List<Map<Node, Node>> permute(ArrayList<Node> nodes)
	{
		return permute(nodes, nodes);
	}
	
	private List<Map<Node, Node>> permute(ArrayList<Node> targets,
		ArrayList<Node> nodes)
	{
		int size = nodes.size();
		List<Map<Node, Node>> permutations;
		Node target = null;
		
		if (targets.size() == 0) {
			permutations = new ArrayList<Map<Node, Node>>(1);
			permutations.add(new HashMap<Node, Node>());
			return permutations;
		} else {
			target = targets.get(0);
			ArrayList<Node> newTargets = new ArrayList<Node>(targets.size()-1);
			for (int i = 1; i < targets.size(); i++) {
				newTargets.add(targets.get(i));
			}
			targets = newTargets;
		}
		
		permutations = new LinkedList<Map<Node, Node>>();
		for (int i = 0; i < size; i++) {
			ArrayList<Node> excluded = new ArrayList<Node>(size - 1);
			for (int j = 0; j < size; j++) {
				if (i != j)
					excluded.add(nodes.get(j));
			}
			
			List<Map<Node, Node>> further = permute(targets, excluded);
			
			for (Map<Node, Node> permuted : further) {
				Map<Node, Node> results = new HashMap<Node, Node>(permuted);
				results.put(target, nodes.get(i));
				permutations.add(results);
			}
		}
		
		return permutations;
	}
	
	public boolean equals(Object other)
	{
		return (other instanceof IsomorphicComparator);
	}
}
